package main

//有一个有序数列 从小到大排列
//1,3,5,8,16,189,212,234
// 找出目标数字189

func BinarySearch(array []int, target int, l, r int) int {
	if l > r {
		//出界了，找不到
		return -1
	}

	//从中间开始找
	mid := (1 + r) / 2
	middleNum := array[mid]

	if middleNum == target {
		//直接找到
		return mid
	} else if middleNum > target {
		//中间数比目标大
		return BinarySearch(array, target, 0, mid-1)
	} else {
		//中间数比目标小
		return BinarySearch(array, target, mid+1, r)
	}
}

func main() {
	array := []int{1, 3, 5, 8, 16, 189, 212, 234}
	target := 189
	BinarySearch(array, target, 0, len(array)-1)
}

//使用非递归法
func BinarySearch2(array []int, target int, l, r int) int {
	ltemp := l
	rtemp := r

	for {
		if ltemp > rtemp {
			//出界 找不到
			return -1
		}
		//从中间开始找
		mid := (ltemp + rtemp) / 2
		middleNum := array[mid]

		if middleNum == target {
			return mid //找到了
		} else if middleNum > target {
			//中间的数比目标还大，从左边找
			rtemp = mid - 1
		} else {
			//中间数比目标小，从右边找
			ltemp = mid + 1
		}
	}
}
